package pers.qianyu.month_202102.date_20210215;

import java.util.*;

/**
 * 438. 找到字符串中所有字母异位词
 * https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
 *
 * @author mizzle rain
 * @date 2021年2月15日19:19:54
 */
public class FindAnagrams2 {
    public List<Integer> findAnagrams(String s, String p) {
        int m = s.length(), n = p.length();
        if (n > m) return new ArrayList<>();
        ArrayList<Integer> res = new ArrayList<>();
        int[] need = new int[26], window = new int[26];
        for (int i = 0; i < n; i++) need[p.charAt(i) - 'a']++;
        int left = 0, right = 0, cnt = 0;
        for (int x : need) if (x > 0) cnt++;
        while (right < m) {
            char c1 = s.charAt(right++);
            window[c1 - 'a']++;
            if (window[c1 - 'a'] == need[c1 - 'a']) cnt--;
            while (cnt == 0) {
                if (right - left == n) res.add(left);
                char c2 = s.charAt(left++);
                if (window[c2 - 'a']-- == need[c2 - 'a']) cnt++;
            }
        }
        return res;
    }
}